本篇同步發布於Blog: [解題] LeetCode - 1094 Car Pooling

平台：

LeetCode

題號：

1094 - Car Pooling

題目連結：

https://leetcode.com/problems/car-pooling/

題目說明：

        輸入N個站點，每個站點有上車的人數、上站點的位置和下站點的位置，而一輛車子有最大的載乘量capaticy，從起點位置0開過去接送這些乘客，是否能全部載完呢？

解題方法：

　　使用貪婪法，將上站與下站位置從小到大排序，而上站人數是正數、下佔人數是負數，capaticy由小的位置開始相減，如果相減過程變負數，則代表載不完。

　　排序的規則還要注意如果遇到同樣上站或下站位置，優先讓下站的排前面，這樣capaticy才有空間。

難度為Medium

程式碼 (C++ 與 C#)：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Passenger{
    int loc;
    int num;
};

bool cmp(const Passenger a, const Passenger b){
    if(a.loc != b.loc)
        return  a.loc < b.loc;
    
    return a.num < b.num;
}

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<Passenger> list;
        for(int i = 0 ; i < trips.size();++i){
            Passenger upPas;
            upPas.loc = trips[i][1];
            upPas.num = trips[i][0];
            list.push_back(upPas);
            
            Passenger downPas;
            downPas.loc = trips[i][2];
            downPas.num = -trips[i][0];
            list.push_back(downPas);
        }
        
        sort(list.begin(), list.end(), cmp);
        
        for(int i = 0 ; i < list.size();++i){
            capacity -= list[i].num;
            if(capacity < 0){
                return false;
            }
        }
        
        return true;
    }
};

int main()
{
    Solution s;
	vector<int> nums1{2,1,5}; 
	vector<int> nums2{3,5,7};
	vector<vector<int>> trips;
	trips.push_back(nums1);
	trips.push_back(nums2);
    cout << s.carPooling(trips, 3) << endl;

    return 0;
}

using System;
using System.Collections.Generic;

namespace LeetCode1094
{
        public class Passenger{
        public int loc;
        public int num;
    }

    public class CMP : IComparer<Passenger> 
    { 
        public int Compare(Passenger a, Passenger b) 
        { 
            if(a.loc != b.loc)
                return  a.loc < b.loc ? -1 : 1;

            return a.num < b.num ? -1 : 1;
        } 
    } 
    

    public class Solution {
        public bool CarPooling(int[][] trips, int capacity) {
            List<Passenger> list = new List<Passenger>();
            for(int i = 0 ; i < trips.Length; ++i){
                Passenger upPas = new Passenger();
                upPas.loc = trips[i][1];
                upPas.num = trips[i][0];
                list.Add(upPas);
                
                Passenger downPas = new Passenger();
                downPas.loc = trips[i][2];
                downPas.num = -trips[i][0];
                list.Add(downPas);
            }
            
            CMP cmp = new CMP(); 
            list.Sort(cmp);

            for(int i = 0 ; i < list.Count;++i){
                capacity -= list[i].num;
                if(capacity < 0){
                    return false;
                }
            }
            
            return true;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            int[][] trips = new int[][]
            {
                new int[] {2,1,5},
                new int[] {3,5,7}
            };
            Console.WriteLine(new Solution().CarPooling(trips, 3));
            Console.Read();
        }
    }
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/1000-1099/1094.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/1000-1099/1094.cs